package 笔试.科大讯飞笔试.第二题快速排序;

import java.util.Arrays;

public class Main
{
    //编程实现该排序算法。
    //输入描述:
    //输入为两行，第一行为序列长度，
    // 9
    // 第二行为序列内容，
    // 如:25 84 21 47 15 27 68 35 20
    //输入要求:
    //1.序列的长度大于等于1
    //2.序列内容要求为整数
    //输出描述:
    //输出为每一轮变化后的序列快照，某-轮序列处理后不变化也输出，如
    //15 20 21 25 47 27 68 35 84
    //15 20 21 25 47 27 68 35 84
    //15 20 21 25 47 27 68 35 84
    //15 20 21 25 35 27 47 68 84
    //15 20 21 25 27 35 47 68 84
    //15 20 21 25 27 35 47 68 84
//
//    作者：.......只想学习
//    链接：https://www.nowcoder.com/discuss/464005?type=post&order=time&pos=&page=1&channel=666&source_id=search_post
//    来源：牛客网

    public static void main(String[] args) {
        int[] arr = {25,84,21,47,15,27,68,35,20};
        quickSort(arr, 0, arr.length - 1);
    }
    public static void quickSort(int[] arr, int low, int high) {
    //!!!!!快排，双指针法
        if(low >= high) return;//这里一定是大于等于 不然和答案不一致
        int left = low, right = high;
        int base = arr[low]; //还有这里
        while(left < right) {
            while(arr[right] >= base && left < right) right--;
            while(arr[left] <= base && left < right) left++;
            if(left < right) swap(arr, left, right);
        }
        arr[low] = arr[left];
        arr[left] = base;
//        System.out.println(Arrays.toString(arr));
        quickSort(arr, low, left-1);
        quickSort(arr, left+1, high);
    }
    public static void swap(int[] arr, int i, int j ) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
